class KMP:
    # 定义一个构建前缀列表的类方法，将原始模式串中的前缀字串，后缀字串的最长共有元素的长度记录下来
    def prefixList(self, pattern, prefix, n):
        prefix[0] = 0
        len = 0
        i = 1
        while i < n:
            if prefix[i] == pattern[len]:
                prefix[i] = len
                len += 1
            else:
                if len > 0:
                    len = prefix[len - 1]
                else:
                    prefix[i] = len
            i += 1

    # 定义移动前缀列表的类方法
    def move(self, prefix, n):
        for i in range(n - 1, 0, -1):
            prefix[i] = prefix[i - 1]
        prefix[0] = -1

    # 定义KMP匹配算法的类方法
    def KMP(self, text, pattern):
        # text表示目标串  pattern表示模式串
        m, n = len(text), len(pattern)
        prefix = [0 for _ in range(n)]
        self.prefixList(pattern, prefix, n)
        self.move(prefix, n)
        i, j = 0, 0
        # i用来循环目标串
        while i < m:
            if j == n - 1 and text[i] == pattern[j]:
                print("匹配成功，模式串在目标串中第{}个位置开始".format(i - j))
                j = prefix[j]
                return
            if text[i] == pattern[j]:
                i += 1
                j += 1
            else:
                j = prefix[j]
                if j == -1:
                    i += 1
                    j += 1
        print("匹配失败,位置为-1")


if __name__ == "__main__":
    text = "FJKABABCABAAFDSF"
    pattern = "KABA"
    kmp = KMP()
    kmp.KMP(text, pattern)
    # 输出结果：匹配成功，模式串在目标串中第10个位置开始
